package 打牢基础30天.day02.my;

import java.util.PriorityQueue;

/**
 * @Author yaya
 * @Create 2024/6/13 9:41
 * Description:每一个元素不移动超过k，使其排序
 */
public class Code04_SortArrayDistanceLessK {

    /**
     * 数组中任意元素排序之后与排序之前的位置差不超过k（k相比数组来说很小）
     * @param arr
     * @param k
     */
    public static void sortArrayDistanceLessK(int[] arr, int k){
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int index = 0;
        for (;index < Math.min(arr.length, k); index++){
            queue.add(arr[index]);
        }
        int i = 0;
        for (; i < arr.length; i++, index++) {
            queue.add(arr[index]);
            arr[i] = queue.poll();
        }
        while (!queue.isEmpty()){
            arr[i++] = queue.poll();
        }
    }
}
